package trees;

import beans.TreeNode;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * @author pengfei.hpf
 * @date 2020/3/21
 * @verdion 1.0.0
 * 1110. 删点成林
 * 给出二叉树的根节点 root，树上每个节点都有一个不同的值。
 *
 * 如果节点值在 to_delete 中出现，我们就把该节点从树上删去，最后得到一个森林（一些不相交的树构成的集合）。
 *
 * 返回森林中的每棵树。你可以按任意顺序组织答案。
 *
 *
 *
 * 示例：
 *
 *
 *
 * 输入：root = [1,2,3,4,5,6,7], to_delete = [3,5]
 * 输出：[[1,2,null,4],[6],[7]]
 *
 *
 * 提示：
 *
 * 树中的节点数最大为 1000。
 * 每个节点都有一个介于 1 到 1000 之间的值，且各不相同。
 * to_delete.length <= 1000
 * to_delete 包含一些从 1 到 1000、各不相同的值。
 */
public class DelNodes {
    List<TreeNode> res = new ArrayList<>();
    public List<TreeNode> delNodes(TreeNode root, int[] to_delete) {
        if(root == null){
            return null;
        }
        Set<Integer> set = new HashSet<>();
        for(int i: to_delete){
            set.add(i);
        }
        root = travel(root, set);
        if(root != null){
            res.add(root);
        }
        return res;
    }

    private TreeNode travel(TreeNode root, Set<Integer> toDel){
        if(root == null){
            return null;
        }
        root.left = travel(root.left, toDel);
        root.right = travel(root.right, toDel);
        if(toDel.contains(root.val)){
            if(root.left != null){
                res.add(root.left);
            }
            if(root.right != null){
                res.add(root.right);
            }
            return null;
        }
        return root;
    }
}
